/**
 * //小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为
 * // root 。
 * //
 * // 除了
 * // root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的
 * //房子在同一天晚上被打劫 ，房屋将自动报警。
 * //
 * // 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
 * //
 * //
 * //
 * // 示例 1:
 * //
 * //
 * //
 * //
 * //输入: root = [3,2,3,null,3,null,1]
 * //输出: 7
 * //解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
 * //
 * // 示例 2:
 * //
 * //
 * //
 * //
 * //输入: root = [3,4,5,1,3,null,1]
 * //输出: 9
 * //解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * //
 * //
 * //
 * // 树的节点数在 [1, 10⁴] 范围内
 * // 0 <= Node.val <= 10⁴
 * //
 * //
 * // Related Topics 树 深度优先搜索 动态规划 二叉树 👍 1397 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

import com.xixi.dataStructure.tree.TreeNode;

public class ID00337HouseRobberIii {
    public static void main(String[] args) {
        Solution solution = new ID00337HouseRobberIii().new Solution();
    }


//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public int rob(TreeNode root) {

            //首先需要先获取两边的sum，再获取root的sum，说明需要用后序遍历

            //每个节点有两重状态，叶子节点只有 偷val  vs 不偷0 两种状态

            TreeNodeStatus rootStatus = backTrack(root);

            return Math.max(rootStatus.stealval, rootStatus.unStealval);

        }


        public TreeNodeStatus backTrack(TreeNode nowNode) {
            //叶子节点如果是null，贡献度都为0
            if (nowNode == null) return new TreeNodeStatus(0, 0);

            TreeNodeStatus thisStatus = new TreeNodeStatus();
            thisStatus.left = backTrack(nowNode.left);
            thisStatus.right = backTrack(nowNode.right);

            //后续遍历，根节点最后遍历
            //如果当前节点要偷，那么两个子节点都不能偷
            thisStatus.stealval = thisStatus.left.unStealval + thisStatus.right.unStealval + nowNode.val;

            //如果当前节点不偷，子节点有四种情况
            //两者都偷
            int bothSteal = thisStatus.left.stealval + thisStatus.right.stealval;
            //两者都不偷
            int bothUnSteal = thisStatus.left.unStealval + thisStatus.right.unStealval;
            //左偷右不偷
            int leftSteal = thisStatus.left.stealval + thisStatus.right.unStealval;
            //右偷左不偷
            int rightSteal = thisStatus.left.unStealval + thisStatus.right.stealval;

            //四种情况取最大值
            thisStatus.unStealval = Math.max(bothSteal, Math.max(bothUnSteal, Math.max(leftSteal, rightSteal)));

            return thisStatus;

        }


        public class TreeNodeStatus {
            int unStealval;
            int stealval;
            TreeNodeStatus left;
            TreeNodeStatus right;

            TreeNodeStatus() {
            }

            TreeNodeStatus(int unStealval, int stealval) {
                this.unStealval = unStealval;
                this.stealval = stealval;
            }

            TreeNodeStatus(int unStealval, int stealval, TreeNodeStatus left, TreeNodeStatus right) {
                this.unStealval = unStealval;
                this.stealval = stealval;
                this.left = left;
                this.right = right;
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}